package offer2

import (
	"math"
	"strconv"
)

/**
原题链接:
https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

B站 帅地玩编程
剑指offer 43.1~n整数中1出现的次数

输入一个整数 n ，求1～n 这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12 这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：
输入：n = 12
输出：5


示例 2：
输入：n = 13
输出：6
*/

/*
思路：
比如算一直到501222，  1出现的次数
     0
     1
     2
   ...
501222

那么先算个位上1的个数，然后再计算十位上1的个数，再计算百位上的1的个数，
依次类推，最后把所有位上1的个数相加即可

那么如何求个位、十位这样位数上1的个数呢？
以计算百位上1的个数为例，
我们的1用bit来表示，bit=100,就表示计算百位数,bit=1000,就表示我们要计算千位数上的1

定义一个cur变量，指向百位数上的数字，
5       0       1       2       2      2
high(501)               cur     low(22)
                        cur = (n/100) % 10
                        low低位 = n % bit
                        high高位 = n/bit/10
那么百位上1的个数为：low数 * high数
0~501 * 0~99 --> 502 * 100
由此可推：某位1的个数 = (high+1) * bit

当求千位数上的数字时，因为千位上为1，是特殊情况，
5 0 1 2 2 2
0~49 * 0~999
50   * 0~222
求1个数公式为：
(high * bit) + (1 + low)

当求万位数中的数字时，因为万位上为0，也是特殊情况，
5 0 1 2 2 2
0~4 *  0~9999
high * bit
*/

func countDigitOne(n int) int {

	str := strconv.Itoa(n) //将数字转为字符串
	len := len(str)        //获取字符串长度
	res := 0               //声明结果

	for i := len - 1; i >= 0; i-- { //从len末尾数组位置开始遍历
		cur, _ := strconv.Atoi(string(str[i])) //当前位的数字
		height, _ := strconv.Atoi(str[:i])     //高位数字
		low, _ := strconv.Atoi(str[i+1:])      //低位数字

		if cur > 1 { //当前位数字 > 1  公式: 当前位1的个数 = (high + 1) * bit位
			res += (height + 1) * int(math.Pow10(len-1-i))
		}
		if cur == 1 { //当前位数字 == 1 公式: 当前位1的个数 = high * bit + low + 1
			res += height*int(math.Pow10(len-1-i)) + low + 1
		}
		if cur == 0 { //当前位数字 == 0 公式: 当前位1的个数 = high * bit
			res += height * int(math.Pow10(len-1-i))
		}

	}

	return res
}
